googologywikiaorg-20200223-history
User blog:Wythagoras/Conway's game of life
Here are some functions I made up using Conway's Game of Life. Informal definition *Die(n) = the maximal number of steps that a configuration of at most n cells can make before dying out. *SS(n) = the maximal number of steps that a configuration of at most n cells can make when stabilizing. (when there is no configuration that stabilizes, this returns 0) *SC(n) = the maximal number of cells that a configuration of at most n cells can have when stabilizing. (when there is no configuration that stabilizes, this returns 0) *NGC(n) = the maximal number of cells that a configuration of at most n cells can have though its number of cells is still bounded above by some number K for all generations. *NGS(n) = the maximal number of steps that a configuration of at most n cells can make though its number of cells is still bounded above by some number K for all generations. *Osc(n) = the maximal period of an oscilliator with at most n cells. The starting patterns must fit in an N2 by N2 square. Formal definitions Let C(P,t) be the number of cells alive at time t (natural number or 0), with a starting pattern P. Let H(P) be the width of the pattern P. (horizontal) Let V(P) be the length of the pattern P. (vertical) Let C be a cell. And A(C,Q,t) is the condition of the cell returns 1 if alive and 0 if dead. Now, let Q be a pattern that statistifies the requirement \(C(Q,0)≤N,H(Q)≤N^2,V(Q)≤N^2\). The following functions are functions from \(\mathbb{N}\) to \(\mathbb{N}\): \(\text{Die}(N) = \text{max}\{t|\exists Q: \wedge C(Q,t-1) \neq 0\}\) \(\text{NGC}(N) =\text{max}\{C(Q,t)|\exists K \forall T: C(Q,T) < K\}\) \(\text{SC}(N)=\text{max}\{C(Q,t)|\forall C: A(C,Q,t) = A(C,Q,t+1)\}\) \(\text{SS}(N)=\text{max}\{t|\exists Q: C: A(C,Q,t) = A(C,Q,t+1)\wedge \exists C: A(C,Q,t-1) \neq A(C,Q,t)\} \) The other 2 will or will not come... 1, 2, 3 cells Die(1), SS(1), SC(1), NGC(1), NGS(1) and Osc(1) 1 cell dies out after one step, so Die(1) = 1. No pattern with 1 cell stabilizes, so SS(1) = SC(1) = 0. NGC(1) is also 0, since a died out doesn't grow in number of cells. But a died out pattern stopped growing, so NGS(1) = 1. (just as Die(1)). Also, no oscilliator with 1 cell exists, but the empty board, so Osc(1) = 1. Die(2), SS(2), SC(2), NGC(2), NGS(2) and Osc(2) 2 cells dies out after one step, so Die(2) = 1. No pattern with 2 cells stabilizes, so SS(2) = SC(2) = 0. NGC(2) is also 0, since a died out doesn't grow in number of cells, but has 0 cells. But a died out pattern stopped growing, so NGS(2) = 1. Also, no oscilliator with 1 cell exists, but the empty board, so Osc(2) = 1. Die(3) and NGS(3) Step 1 Step 2 Step 3 x x x x x So this proves NGS(3) ≥ Die(3) ≥ 2. By analysing all configurations it can be proven that NGS(3) = Die(3) = 2. SS(3) and SC(3) and NGC(3) SS(3) = 1 and NGC(3) = SC(3) = 4. Step 1 Step 2 x xx xx xx Osc(3) Osc(3) = 2. Step 1 Step 2 x xxx x x Some sort of an idea We can build some sort of a Turing Machine on this.... We have a machine with N states. Every state can specify a rule. (The rule is presented as S/B, being S the cells that survive if they have that many neighbours, and B being the cells that are born when they have that many neighbours. So Conway's life is 23/3.). Furthermore, a new state is specified. Also, a begin situation with N cells is specified. Now, Life(N) is the maximal number of steps that a configuration with N states and N cells can make before stopping growing in number of cells. I have no idea whether its well defined or not. Category:Blog posts